//Given an integer array nums, find a contiguous non-empty subarray within the a
//rray that has the largest product, and return the product. 
//
// It is guaranteed that the answer will fit in a 32-bit integer. 
//
// A subarray is a contiguous subsequence of the array. 
//
// 
// Example 1: 
//
// 
//Input: nums = [2,3,-2,4]
//Output: 6
//Explanation: [2,3] has the largest product 6.
// 
//
// Example 2: 
//
// 
//Input: nums = [-2,0,-1]
//Output: 0
//Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 2 * 104 
// -10 <= nums[i] <= 10 
// The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit 
//integer. 
// 
// Related Topics 数组 动态规划 
// 👍 1142 👎 0

package leetcode.editor.cn;

class P152MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new P152MaximumProductSubarray().new Solution();
        System.out.println(solution.maxProduct(new int[]{-1, -2, -9, -6}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProduct(int[] nums) {
            int len = nums.length;
            int maxF = nums[0];
            int minF = nums[0];
            int max = nums[0];
            for (int i = 1; i < len; i++) {
                int maxf = maxF, minf = minF;
                maxF = Math.max(Math.max(maxf * nums[i], nums[i]), minf * nums[i]);
                minF = Math.min(Math.min(maxf * nums[i], nums[i]), minf * nums[i]);
                max = Math.max(Math.max(maxF, minF), max);
            }

            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}